package com.cn.codebrush.动态规划;

public class No38外观数列 {
    public static void main(String[] args) {
        System.out.println(countAndSay2(4));
    }


    /**
     * 优化方法一
     * @param n
     * @return
     */
    public static String countAndSay2(int n) {
        String res = "1";
        for(int i=1;i<n;i++){
            String str = res;
            String resStr = "";
            for(int j=0;j<str.length();j++){
                String temp = str.charAt(j)+"";
                int count = 1;
                while(j<str.length()-1 && str.charAt(j+1) == str.charAt(j)){
                    count++;
                    j++;
                }
                resStr += count + temp;

            }
           res = resStr;
        }

        return res;
    }
    /**
     * 解法一
     * @param n
     * @return
     */
    public static String countAndSay(int n) {
        String[] dp = new String[n];
        dp[0] = "1";
        for(int i=1;i<n;i++){
            String str = dp[i-1];
            String[] strs = str.split("");
            String resStr = "";
            for(int j=0;j<strs.length;j++){
                String temp = strs[j];
                int count = 1;
                while(j<strs.length-1 && strs[j+1].equals(strs[j])){
                    count++;
                    j++;
                }
                resStr += count + temp;
            }
            dp[i] = resStr;
        }

        return dp[n-1];
    }
}
